package q757_intersectionSizeTwo;

import java.util.Arrays;

/*
此题主要采用贪心算法，可以参考q452 使用最少的箭戳破气球
1、首先按照右端点从小到大排序；
2、不妨让p1和p2代表目前所选择区间中的最大两个数，那么初始值就应该是第一个区间的右端点处的两个值，
原因是：尽量选取靠右的数字可以增大与后边区间相交的可能性；
3、于是就从第二个区间开始验证，假设俩数字都在区间内，那么无需处理；
4、假如较大的数字都不在区间内，说明俩数都不在区间内，那么需要增加俩数字，也就是将这个区间的最右端的俩点换上（这里由于已经按右端点排序了，所以新的俩点肯定分别大于旧的俩点）；
5、假如较大的数字在区间内，但是较小的数字不在，那么需要多加一个数（尽量少换数字，因为题目问的是最小数量），
这里分两种情况：
1）此时较大的数字是右端点，那么需要把较小的数字移动到较大数字的左侧即可；
2）否则，较小的数字变成此时的较大的数字，较大的数字变成区间的右端点
 */
public class Solution {
    public int intersectionSizeTwo(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[1] == o2[1]) return o2[0] - o1[0];
            return o1[1] - o2[1];
        });
        int ans = 2;
        int p1 = intervals[0][1] - 1, p2 = intervals[0][1];
        for (int[] interval : intervals) {
            int l = interval[0], r = interval[1];
            if (l <= p1) {
                continue;
            } else if (l <= p2) {
                ++ans;
                p1 = l;
                p2 = r;
            } else {
                ans += 2;
                p1 = r - 1;
                p2 = r;
            }
        }

        return ans;
    }
}
